package com.clps.algorithm03.链表;

/**
 * 链表的插入为3中,一种是头部插入,一种是尾部插入,一种是中间插入,在头部插入完之后要更新head节点,在尾部插入后要更新tail节点,如图所示
 *
 */
public class 单向链表 {

    private  LinkNode head; //头节点
    private  LinkNode tail;//尾结点
    private  int size;//链表的长度

    
    //在尾部廷加节点
    public void add(int val){
        insert(size,val);
    }
    //删除节点
    public int poll(){
        return  remove1(0);
    }

    //节点个数
    public int size(){
        return size;
    }

    //清空链表
    public void  clear(){
        while (head!=null){
            LinkNode next = head.next;
            head.next = head;//指向自己
            head = next;
        }
        tail = null;
        size = 0;
    }


    private void insert(int index, int val) {
        if(index ==0){//插入的是头节点
            head = new LinkNode(val,head);//创建一个头节点赋值给head
            if(size ==0){//如果之前的链表为空,让tail也指向head
                tail = head;
            }
        }else if(index == size){ //在链表的尾部插入
            tail.next = new LinkNode(val,null);//在创建尾结点
            tail = tail.next;
        }else{ //不再末尾添加
            LinkNode preNode = findPre(index);//查找index节点的前一个节点
            preNode.next = new LinkNode(val,preNode.next);
        }
        size++;//节点个数加1
    }

    //查找index节点的前一个节点
    private LinkNode findPre(int index) {
        //index必须是有效的,不能越界,查找前一个,index可以等于size
        if(index<0 || index>size){
            throw  new IndexOutOfBoundsException("越界异常");
        }
        if(index ==0){ //头节点的前一个节点为空
            return  null;
        }

        LinkNode preNode= head;
        for (int i = 0; i <index-1 ; i++) {
            preNode = preNode.next;
        }
        return preNode;
    }


    private int remove1(int index) {
        if(size ==0){
            throw  new IllegalStateException("链表是空的,没法删除.....");
        }
        LinkNode delete;//待删除的节点
        if(index ==0){ //删除的是头节点
            delete = head;//记录待删除的节点
            head = head.next;//更新head节点
            if(head == null){//如果链表为空,让tail也为空
                tail = null;
            }
        }else{//删除的不是头节点
            LinkNode preNode = findPre(index);//查找删除的节点前一个节点
            if(index == size-1){ //删除的是尾节点
                delete = preNode.next;
                preNode = preNode.next;
                preNode.next = null;//删除
            }else{ //删除的是中间节点
                delete = preNode.next;
                preNode.next = delete.next;
            }
        }
        delete.next = delete;
        size--;//节点个数减去1
        return delete.val;
    }

    public static void main(String[] args) {
        单向链表 demo01 = new 单向链表();
        int size1 = demo01.size;
        int[] nums2 = {1, 2, 3};
        demo01.add(1);
        System.out.println("size1 = " + size1);
    }
}
